package leetcode_day._2021._202112._2131;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/29 9:25
 * 统计特殊四元组
 * 算法：数组、哈希表
 */
public class _29_1995 {

    public int countQuadruplets(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int m = k + 1; m < n; m++) {
                        if (nums[i] + nums[j] + nums[k] == nums[m]) ++ans;
                    }
                }
            }
        }
        return ans;
    }

    /**
     * 倒序遍历 c，这样 d 的范围就大了
     * 然后把 d 的数量记录下来
     * @param nums
     * @return
     */
    public int countQuadruplets_hash(int[] nums) {
        int ans = 0, n = nums.length;
        int[] cnt = new int[5000];
        for (int c = n - 2; c >= 2; c--) {
            cnt[nums[c + 1]]++;
            for (int a = 0; a < c; a++) {
                for (int b = a + 1; b < c; b++) ans += cnt[nums[a] + nums[b] + nums[c]];
            }
        }
        return ans;
    }

    /**
     * nums[a] + nums[b] + 200 = nums[d] - nums[c] + 200
     * +200 防止相减为负数
     * 倒序遍历 n
     * @param nums nums
     * @return int
     */
    public int countQuadruplets_hash_up(int[] nums) {
        int ans = 0, n = nums.length;
        int[] cnt = new int[10010];
        for (int b = n - 3; b >= 1; b--) {
            for (int d = b + 2; d < n; d++) cnt[nums[d] - nums[b + 1] + 200]++;
            for (int a = 0; a < b; a++) ans += cnt[nums[a] + nums[b] + 200];
        }
        return ans;
    }

}
